package com.honeywen.mymvc.leetcode;

import java.util.Stack;

/**
 * 67. 二进制求和
 * https://leetcode-cn.com/problems/add-binary/description/
 *
 * @author weiw@opera.com
 * @date 2018/10/7 上午8:43
 */
public class BinaryAddTest {

    public static void main(String[] args) {
        System.out.println(addBinary("1010", "1011"));

    }

    public static String addBinary(String a, String b) {

        if (a == null || a.length() == 0) {
            return b;
        }
        if (b == null || b.length() == 0) {
            return a;
        }

        int i = a.length() - 1;
        int j = b.length() - 1;


        Stack<Integer> stack = new Stack();
        int max = Math.max(i, j);


        boolean add = false;
        int x, y = 0;
        for (int k = max; k >= 0; k--, i--, j--) {

            if (i < 0) {
                x = 0;
            } else {

                x = Integer.parseInt(String.valueOf(a.charAt(i)));
            }

            if (j < 0) {

                y = 0;
            } else {
                y = Integer.parseInt(String.valueOf(b.charAt(j)));

            }


            int r = x + y;

            if (add) {
                r++;
            }
            if (r > 1) {
                add = true;
            } else {
                add = false;
            }
            stack.push(r % 2);

        }


        if (add) {
            stack.push(1);
        }

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }

        return sb.toString();

    }
}
